package ninthDay.third;

public class insert {
    public Node insert(Node head, int insertVal) {
        if (head == null){
            Node node = new Node(insertVal);
            node.next = node;
            return node;
        } else if (head.next == null) {
            head.next = new Node(insertVal,head);
            return head;
        }
        Node left = head;
        Node right = head.next;
        Node mid = head;
        while (right != mid){
            if (insertVal <= right.val && insertVal > left.val){
                Node tmp = new Node(insertVal,right);
                left.next = tmp;
                return head;
            } else if (right.val < left.val && (insertVal >= left.val || insertVal <= right.val)) {
                Node tmp = new Node(insertVal,right);
                left.next = tmp;
                return head;
            }
            left = right;
            right = right.next;
        }
        Node tmp2 = new Node(insertVal,right);
        left.next = tmp2;
        return head;
    }
}
